FIFO queues are well known in the art of computing. FIFO queues can be implemented in software or hardware. Typically, a hardware-implemented FIFO queue integrates a memory device with associated on-chip logic, which can be utilized in a wide variety of applications that may require data to be buffered.
A FIFO queue gets its name (that is, First In First Out) from the fact that the data buffered in the FIFO queue's memory is retrieved from the FIFO queue's memory in the same order that it was written to the FIFO queue's memory. That is, the First data element to be stored In the FIFO queue's memory is the First data element to be retrieved Out of the FIFO queue's memory. Similarly, the last data element to be stored in the FIFO queue is the last data element to be retrieved from the queue. The operation of storing a data element in the FIFO queue's memory is generally referred to as a “write” or a “push.” The operation of retrieving a data element from the FIFO queue's memory is generally referred to as a “read” or a “pop.”
A conventional FIFO queue typically comprises storage elements, a write pointer, a write signal, a read pointer, a read signal, a full signal, an empty signal, and a reset signal. The storage elements are used for storing data and can be thought of as memory locations where each memory location has an address. The data stored in the storage elements may be referred to herein as data elements. The write pointer contains the address of the storage element where the next data element is to be written. That is, the write pointer “points to” the storage element into which the next data element will be written. The write signal is an input signal that is asserted to cause a data element to be written into the FIFO queue's storage element pointed to by the write pointer. When the write signal is asserted a data element is written into the storage element pointed to by the write pointer. The read pointer contains the address of the storage element containing the next data element to be retrieved or read from the FIFO queue's storage elements. That is, the read pointer points to the storage element containing the next data element to be read. The read signal is an input signal that is asserted to cause a data element to be read from one of the FIFO queue's storage elements. When the read signal is asserted the data element pointed to by the read pointer is retrieved or read. A full signal is an output signal that is asserted to indicate that the FIFO queue's storage elements are full and no more data can be written into the FIFO queue's storage elements. In other words, the full signal is asserted when the FIFO queue is full. An empty signal is an output signal that is asserted to indicate that the FIFO queue's storage elements are empty and that no data is available to be read from the FIFO queue's storage elements. In other words, the empty signal is asserted when the FIFO queue is empty. A reset signal is an input signal that causes the FIFO queue to become empty.
Conventional FIFO queues have the property that each data element stored in the FIFO queue can be read from the FIFO queue only once. This is because the read pointer is incremented every time a data element is read from the FIFO queue. Once the read pointer is incremented, the storage element just read from becomes available to be written to and the previous data element can then be overwritten and lost. However, in some applications it may be desirable to read some data elements more than once. This may happen, for example, while stepping through a loop construct in a computer program. Thus, in applications where it is desirable to read some data elements more than once conventional FIFO queues are not well suited.